package Outils;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

import Noyau.Chariot;
import Noyau.Chemin;
import Noyau.ObjetMetier;

public class Dijkstra {

	public static DijkstraResult computeShortestPaths(Chemin source)
	{
		// We compute the shortest paths from this node to all the other nodes, and store the distances in dist.
		Map<Chemin, Double> dist = new HashMap<Chemin, Double>();
		Map<Chemin, Chemin> previous = new HashMap<Chemin, Chemin>();
		List<Chemin> allNodes = new ArrayList<Chemin>();

		for (Chemin chemin : source.getAeroport().getChemins()) 
		{
			dist.put(chemin, Double.MAX_VALUE);
			previous.put(chemin, null);		
			allNodes.add(chemin);
		}

		dist.put(source, 0.0);			

		boolean continueSearch = true;			
		while (!allNodes.isEmpty() && continueSearch)
		{
			// We find the parcours in dist with the lower value.
			Double minDistValue = Double.MAX_VALUE;
			Chemin minDistParcours = null;
			for (Map.Entry<Chemin, Double> distEntry : dist.entrySet()) 
			{
				if (allNodes.contains(distEntry.getKey()) && distEntry.getValue() < minDistValue)
				{
					minDistValue = distEntry.getValue();
					minDistParcours = distEntry.getKey();
				}
			}

			// If we found none, we return.
			if (minDistParcours == null)
			{
				continueSearch = false;
				break;
			}

			allNodes.remove(minDistParcours);

			for (Chemin neighbor : minDistParcours.getNeighbors()) 
			{
				double alt = dist.get(minDistParcours) + neighbor.getSize();
				if (alt < dist.get(neighbor))
				{
					dist.put(neighbor, alt);
					previous.put(neighbor, minDistParcours);
				}
			}			
		}

		return new DijkstraResult(dist, previous);
	}

	public static Chemin getNextElement(Map<Chemin, Chemin> previous, Chemin source, Chemin target)
	{
		// Goes backward in the graph to find the first element from here to the target
		Chemin previousNode = previous.get(target);

		while (previousNode != null && previousNode != source)
		{
			target = previousNode;
			previousNode = previous.get(target);
		}

		return target;
	}	
}